package binaryTree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTreePaths {

    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> res = new ArrayList<>();
   if (root==null){
       return  res;
   }
   ArrayList<Integer> paths = new ArrayList<>();
   traveral(root,paths,res);
       return  res;

    }

    //前 中 后序 遍历都是  根节点处处理逻辑  而左右节点处 进行遍历

    private   void  traveral(TreeNode  root,List<Integer> paths,List<String> res){
      paths.add(root.val);
//      递归终止条件
  if (root.left==null&&root.right==null){
      StringBuffer stringBuffer = new StringBuffer();
      for (int i = 0; i <paths.size()-1 ; i++) {
          stringBuffer.append(paths.get(i)).append("->");
      }
      stringBuffer.append(paths.get(paths.size()-1));
      res.add(stringBuffer.toString());
      return;
  }

//  左节点遍历
  if (root.left!=null){
      traveral(root.left,paths,res);
      paths.remove(paths.size()-1);     //回溯
  }
  if (root.right!=null){
      traveral(root.right,paths,res);
      paths.remove(paths.size()-1);  //回溯
  }
    }

    public static void main(String[] args) {
        TreeNode root= new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(3);
        TreeNode treeNode2=new TreeNode(1);
        TreeNode treeNode3 = new TreeNode(2);
        TreeNode treeNode4= new TreeNode(6);
        root.left=treeNode1;
        root.right=treeNode3;
        treeNode1.left=treeNode2;
        treeNode3.right=treeNode4;

        BinaryTreePaths binaryTreePaths = new BinaryTreePaths();

        List<String> strings = binaryTreePaths.binaryTreePaths(root);
        for (String  a:
                strings
             ) {
            System.out.println(a);

        }


    }
}
